/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sorting;

/**
 *
 * @author Adrian Martinez (Bubblesort), Maria Fernanda Martinez (Mergesort),
 * Darwin Rivas (Quicksort), Nery Giron (Insertionsort)
 * Metodos tomados de Java Structures de Duane A. Bailey, capítulo 6
 * 
 */
public class Sort {
    private static void merge(Comparable data[], Comparable temp[], int low, int middle, int high)
    {
        int ri = low; // indice del resultado
        int ti = low; // indice de temp
        int di = middle; // indice de data (destino)
        
        // Mientras las litas no esten vacias, agregar el valor mas pequeño
        while (ti < middle && di <= high)
        {
            if (data[di].compareTo(temp[ti])<0) {
                data[ri++] = data[di++]; // el mas pequeño esta en data
            } else {
                data[ri++] = temp[ti++]; // el mas pequeño esta en temp
            }
        }
        
        // Algunos valores pueden haber quedado en temp
        while (ti < middle)
        {
            data[ri++] = temp[ti++];
        }
        // ...o algunos valores quedaron en data (en el lugar correcto)
    }
    
    /**
     * Nombre: mergeSortRecursive
     * Descripcion: 
     * Pre: 0 <= low <= high < data.length
     * Post: los valores en data[low..high] estan en orden ascendente
     * @param data de tipo int[]
     * @param temp de tipo int[]
     * @param low de tipo int
     * @param high de tipo int
     * Valor de retorno: ninguno
     */
    private static void mergeSortRecursive(Comparable data[], Comparable temp[], int low, int high)
    {
        int n = high-low+1;
        int middle = low + n/2;
        int i;
        
        if (n < 2) return;
        
        // mover la mitad que corresponde a los valores pequeños a un arreglo temporal
        for (i = low; i < middle; i++)
        {
            temp[i] = data[i];
        }
        
        // ordenar la mitad que corresponde a los valores pequeños
        mergeSortRecursive(temp,data,low,middle-1);
        
        // ordenar la mitad que corresponde a los valores grandes
        mergeSortRecursive(data,temp,middle,high);
        
        // unir las mitades
        merge(data,temp,low,middle,high);
    }
    
    /**
     * Nombre: mergeSort
     * Descripcion: accede a mergeSortRecursive 
     * Pre: 0 <= n <= data.length
     * Post: valeres en data[0..n-1] estan en orden ascendente
     * @param data de tipo int[]
     * @param n de tipo int
     */
    public static void mergeSort(Comparable data[], int n)
    {
        mergeSortRecursive(data,new Comparable[n],0,n-1);
    }
     
    
   public static void bubbleSort(Comparable data[], int n){
    int numSorted = 0; // number of values in order
    int index; // general index
    while (numSorted < n)
        {
        // bubble a large element to higher array index
        for (index = 1; index < n-numSorted; index++)
        {
        if (data[index-1].compareTo(data[index])>0)
            swap(data,index-1,index);
        }
    // at least one more value in place
    numSorted++;
    }
} 
    public static void insertionSort(Comparable data[], int n)
    // pre: 0 <= n <= data.length
    // post: values in data[0..n-1] are in ascending order
    {
    int numSorted = 1; // number of values in place
    int index; // general index
    while (numSorted < n)
        {
        // take the first unsorted value
        Comparable temp = data[numSorted];
        // ...and insert it among the sorted:
            for (index = numSorted; index > 0; index--)
            {
                if (temp.compareTo(data[index-1])<0)
                {
                    data[index] = data[index-1];
                } else
                    {
                        break;
                    }
            }
        // reinsert value
        data[index] = temp;
        numSorted++;
        }
}
    /**
     * Nombre: Quick
     * Descripcion: ordena una lista de menor a mayor utilizando un pivote de referencia,  
     * intercambia estos dos cuando la izquierda es mayor a la derecha left>right
     * Pre: los valores de data[] no estan ordenados
     * Post: data[left...right] contiene todos los valores en orden ascendente
     * @param data de tipo int[]
     * @param right de tipo int
     * @param left de tipo int
     * Valor de retorno: ninguno
     */
    
    private static int partition ( Comparable data [] , int left , int right )
// pre : left <= right
// post : data [left] colocada en la posicion (retornada) correcta
{
while (true)
{
// mueve right "pointer" hacia left (izquierda)
    while (left < right && data [left].compareTo(data [right]) <0 ) 
    {
        right--;
    }
    if ( left < right)  
        swap(data , left++ , right ) ;
    else 
        return left;
     

// mueve left pointer hacia right (derecha)
    while(left < right && data [left].compareTo(data [right]) < 0 ) 
    {
        left++ ;
    }
    if ( left < right ) 
        swap(data , left, right--);
    else 
        return right ;
    }
}
    
  public static void quickSort( Comparable data [] , int n)
// post : the values in data [0 . . n- 1] are in ascending order
{
    quickSortRecursive (data , 0 , n- 1 ) ;
}
    private static void quickSortRecursive ( Comparable data [] , int left , int right )
// pre : left <= right
// post : data [left . . right] en orden ascendete
{
    int pivot ; // la posicion final del valor mas alejado de la izquierda
    if (left >= right ) return ;
    pivot = partition (data , left , right ) ; /* 1 - coloca pivot */
    quickSortRecursive (data , left , pivot - 1 ) ; /* 2 - sort small */
    quickSortRecursive (data , pivot+1 , right ) ; /* 3 - sort large */
/* done ! */
}

    public static void swap ( Comparable data [] , int i , int j )
{
Comparable temp ;
temp = data [i] ;
data [i] = data [j] ;
data [j] = temp ;
/** metodo: swap
 * descripcion: intercambia los valores de data[] en los indices i e j
 * pre : 0 <= i , j < data . length
 * post : data [i] y data [j ] son intercambiados
 * @param temp de tipo int
 * @param data de tipo int[]
 * @param i de tipo int
 * @param j de tipo int
 * valor de retorno ninguno
 */

}
    private static int right;
    private static int left;
}
